package demo.practice.leetcode;


import java.util.Arrays;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class P347 {

    public static void main(String[] args) {
        int t[] = {5,3,1,1,1,3,73,1};
        P347 p347 = new P347();
        int[] ints = p347.topKFrequent(t, 2);

    }

    class KV implements Comparable<KV> {    //可以使用Comparable的实现类作为泛型参数
        Integer k;  //词语
        Integer v;  //频率

        public Integer getK() {
            return k;
        }

        public Integer getV() {
            return v;
        }

        @Override
        public int compareTo(KV o) {
            return this.getV() - o.getV();
        }
    }

    public int[] topKFrequent(int[] nums, int k) {

        //PriorityQueue<E>   泛型参数 实现


        TreeMap<Integer, Integer> map = new TreeMap<>();


        Arrays.stream(nums).forEach(i -> {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                (i, j) -> map.get(i) - map.get(j)
        );
//        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer key = entry.getKey();
            if (queue.size() < k) {
                queue.add(key);
            } else if(map.get(key) > map.get(queue.peek()) ) {
                queue.remove();//删除 顶部最小的
                queue.add(entry.getKey());
            }
        }


        int[] res = new int[k];
        for (int i = 0; i < res.length; i++) {
           res[i]=queue.remove();
        }

        return res;
    }
}
